package leetcode.biweekly.week94;

//Solution3Test 118445846
public class Solution3 {

	public int minimizeSet(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
		long ans = 0;
		long l = 0, r = (long) 1e11;
		long lcm = lcm(divisor1, divisor2);
		while (l <= r) {
			long m = ((r - l) >> 1) + l;
			long m1 = m / divisor1;
			long m2 = m / divisor2;
			long m12 = m / lcm;
			long unq = m - m1 - m2 + m12;
			long cur1 = m - m1 - unq;
			long cur2 = m - m2 - unq;
			if (m - m1 >= uniqueCnt1 && m - m2 >= uniqueCnt2 && cur1 + cur2 + unq >= uniqueCnt1 + uniqueCnt2) {
				ans = m;
				r = m - 1;
			} else {
				l = m + 1;
			}
		}
		return (int) ans;
	}

	public long gcd(long a, long b) {
		return b == 0 ? a : gcd(b, a % b);
	}

	public long lcm(long a, long b) {
		return a * b / gcd(a, b);
	}
}
